package com.sf;

import java.util.ArrayList;
import java.util.Collections;

public class MiddleSearch {
public static void main(String[] args) {
        int[] arr = {2, 5, 8, 13, 16, 18, 19, 24, 29, 30};
        int index = middleSearch(arr, 13);
        System.out.println(index+":"+arr[index]);


        int[] arr1 = {13, 2, 8, 5, 30, 18, 29, 1, 19, 16};
        puple(arr1, arr1.length);
        System.out.println("==mao====最终结果========");
        for(int i = 0 ; i < arr1.length; i++) {
            System.out.print(arr1[i]+",");
        }
        System.out.println();
        int[] arr2 = {13, 2, 8, 5, 30, 18, 29, 1, 19, 16};
        insertSorted(arr2);
        System.out.println("==cha====最终结果========");
        for(int i = 0 ; i < arr2.length; i++) {
            System.out.print(arr2[i]+",");
        }
    System.out.println();
    System.out.println("==fast===================");
    System.out.println("==fast====最终结果========");
    int[] arr3 = {13, 2, 8, 5, 30, 18, 11, 1, 19, 16};
    fastSort(arr3,0, 9);
    for(int i = 0 ; i < arr3.length; i++) {
        System.out.print(arr3[i]+",");
    }

    System.out.println();
    System.out.println("==归并===================");
    System.out.println("==归并====最终结果========");
    int[] arr5 = {13, 2, 8, 5, 30, 18, 11, 1, 19, 16};
    mergeSort(arr5);
    printArray(arr5);

    System.out.println();
    System.out.println("==桶排序===================");
    System.out.println("==桶排序====最终结果========");
    int[] arr6 = {13, 2, 8, 5, 30, 18, 11, 1, 19, 16};
    bucketSort(arr6);
    printArray(arr6);
    }

    public static int middleSearch(int[] arr, int a) {
        int lo = 0;
        int hi = arr.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (arr[mid] == a) {
                return mid;
            } else if (arr[mid] > a) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
            System.out.println("mid="+mid+"--lo:"+lo+"--hi:"+hi);
        }
        return -1;
    }

    /**
     * 将大值沉到最后
     * 13@, 2, 8, 5, 30, 18, 29, 1, 19, 16
         2, 8, 5, 13,18, 29,  1,19, 16, 30,---
         2, 5, 8, 13,18,  1, 19,16, 29, 30,---
         2, 5, 8, 13, 1, 18, 16,19, 29, 30,---
         2, 5, 8,  1,13, 16, 18,19, 29, 30,---
         2, 5, 1,  8,13, 16, 18,19, 29, 30,---
         2, 1, 5,  8,13, 16, 18,19, 29, 30,---
         1, 2, 5,  8,13, 16, 18,19, 29, 30,---
         1, 2, 5,  8,13, 16, 18,19, 29, 30,---
         1, 2, 5,  8,13, 16, 18,19, 29, 30,---
         1, 2, 5,  8,13, 16, 18, 19,29, 30,---
         1, 2, 5,  8,13, 16, 18, 19,29, 30,
     *
     * @param arr
     * @param n
     */
    public static void puple(int[] arr, int n) {
        for(int i = 0; i < n; i++) {
            boolean isBreak = true;
            for(int j = 1; j < n-i; j++) {
                if(arr[j-1] > arr[j]) {
                    int temp;
                    temp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                    isBreak = false;
                }
            }
            if(isBreak) {
                break;
            }
            for(int k = 0; k < n; k++) {
                System.out.print(arr[k]+",");
            }
            System.out.println("---");
        }
    }

    /**
     *
     * 13, 2@, 8, 5, 30, 18, 29, 1, 19, 16
     *  2,13 , 8@,5, 30, 18, 29, 1, 19, 16
     *  2, 8 ,13 ,5@, 30, 18, 29, 1, 19, 16
     *  2, 5 , 8 ,13, 30@, 18, 29, 1, 19, 16
     *  2, 5 , 8 ,13, 30, 18@, 29, 1, 19, 16
     *  2, 5 , 8 ,13, 18, 30
     *
     * */
    public static void insertSorted(int arr[]) {

        for(int i = 1; i < arr.length; i++) {

            //插入数
            int insertVal = arr[i];                              //2
            //被插入位置
            int index = i-1;                                     //0

            while(index>=0 && insertVal < arr[index]) {
                arr[index+1] = arr[index];
                index--;
            }

            arr[index+1] = insertVal;

            for(int k = 0; k < arr.length; k++) {
                System.out.print(arr[k]+",");
            }
            System.out.println("---");
        }


    }

    /**
     * {13, 2, 8, 5, 30, 18, 29, 1, 19, 16};
     * @param array
     * @param low
     * @param high
     */
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pi = partition(array, low, high);
            quickSort(array, low, pi - 1);  // 对左子数组进行递归排序
            quickSort(array, pi + 1, high); // 对右子数组进行递归排序
        }
    }

    /**
     *  {13, 2, 8, 5, 30, 18, 29, 1, 19, 16@};
     *
     * @param array
     * @param low
     * @param high
     * @return
     */
    private static int partition(int[] array, int low, int high) {
        int pivot = array[high];  // 选择最后一个元素作为基准
        int i = (low - 1);  // 较小元素的索引
        for (int j = low; j < high; j++) {
            if (array[j] <= pivot) {
                i++;
                System.out.println("=i,j="+i+"--"+j);
                // 交换array[i]和array[j]
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        System.out.println();
        System.out.println("=====交换前=====");
        printArray(array);
        // 交换array[i+1]和array[high] (或基准)
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;
        System.out.println();
        System.out.println("=====交换后=====");
        printArray(array);

        return i + 1;
    }

    private static void printArray(int[] arr) {
        for(int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+"    ");
        }
    }

    /**
     * 13*	2	8	5	30	18	11	1	19	16
     * 1    2   8   5   30  18  11  13  19  16
     * @param arr
     * @param low
     * @param high
     */
    private static void fastSort(int[] arr, int low, int high) {
        int start = low;
        int end = high;
        int key = arr[low];
        while(end>start){
            //从后往前比较
            while(end>start&&arr[end]>=key)
                //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
                end--;
            if(arr[end]<=key){
                int temp = arr[end];
                arr[end] = arr[start];
                arr[start] = temp;
            }   //1    2   8   5   30  18  11  13  19  16
                //1    2   8   5   11  18  13  30  19  16  start=4 end=6

            //从前往后比较
            while(end>start&&arr[start]<=key)
            //如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
                start++;
            if(arr[start]>=key){
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
            }  //1    2   8   5   13  18  11  30  19  16
            // end = 7, start = 4
            //此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的
            //值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
        }
        //递归
        //1 2 8 5
        if(start>low) fastSort(arr,low,start-1);//左边序列。第一个索引位置到关键值索引-1
        //18 29 30 19 16
        if(end<high) fastSort(arr,end+1,high);//右边序列。从关键值索引+1 到最后一个
    }


    private static void mergeSort(int[] arr) {
        mergeSortInner(arr, 0, arr.length-1);
    }

    /**
     * {13, 2, 8, 5, 30, 18, 11, 1, 19, 16};
     * 5
     * 2
     * 1
     * 0 9
     * 0 4
     * 0 2
     * 0 1
     * 归并排序算法
     * @param arr
     * @param left
     * @param right
     */
    private static void mergeSortInner(int[] arr, int left, int right) {
        System.out.println("==1==left==="+left+"--"+"======right==="+right);
        if(left >= right) {
            System.out.println("==2==left==="+left+"--"+"======right==="+right);
            return;
        }
        int mid = (left + right) / 2;
        mergeSortInner(arr, left, mid);  // left:0, right:1
                                         // left:0, right:2
                                         // left:0, right:4
                                         // left:0, right:9
        mergeSortInner(arr, mid + 1, right);
        merge(arr, left, mid, right);    // left:0, mid:0, right:1
    }

    private static void merge(int[] data, int left, int center, int right) {
        // 临时数组
        int[] tmpArr = new int[data.length];
        // 右数组第一个元素索引
        int mid = center + 1;  //1
        // third 记录临时数组的索引
        int third = left;      //0
        // 缓存左数组第一个元素的索引
        int tmp = left;        //0
        while (left <= center && mid <= right) {
            // 从两个数组中取出最小的放入临时数组
            if (data[left] <= data[mid]) {
                tmpArr[third++] = data[left++];
            } else {
                tmpArr[third++] = data[mid++];
            }
        }
        // 剩余部分依次放入临时数组（实际上两个 while 只会执行其中一个）
        while (mid <= right) {
            tmpArr[third++] = data[mid++];
        }
        while (left <= center) {
            tmpArr[third++] = data[left++];
        }
        // 将临时数组中的内容拷贝回原数组中
        // （原 left-right 范围的内容被复制回原数组）
        while (tmp <= right) {
            data[tmp] = tmpArr[tmp++];
        }
    }

    public static void bucketSort(int[] arr) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        //创建桶
        int bucketNum = (max - min) / arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketArr.add(new ArrayList<Integer>());
        }
        //将每个元素放入桶
        for (int i = 0; i < arr.length; i++) {
            int num = (arr[i] - min) / (arr.length);
            bucketArr.get(num).add(arr[i]);
        }
        //对每个桶进行排序
        for (int i = 0; i < bucketArr.size(); i++) {
            Collections.sort(bucketArr.get(i));
        }
        for(int i = 0; i < bucketArr.size(); i++) {
            for (int j = 0; j < bucketArr.get(i).size(); j++) {
                System.out.print(bucketArr.get(i).get(j)+",");
            }
        }
        System.out.println();
    }
}
